package com.Algorithm.leetcode.Study;

import java.util.HashMap;

/**
 * Created with IntelliJ IDEA.
 *
 * @Author: zjz
 * @Date: 2021/10/18/9:10
 * @Description:
 * @Target:
 */
public class Code06_CopyListWithRandom {

    public static class Node {
        public int value;
        public Node next;
        public Node rand;

        public Node(int data) {
            this.value = data;
        }
    }
    /*
    * 用hash表存放Node对象,Node.val,Node.next Node.rand;
    * 实现链表复制
    *
    * */



    public static Node copyListWithRand1(Node head) {
        HashMap<Node, Node> map = new HashMap<Node, Node>();  // 定义hash表
        Node cur = head;  // 当前节点的指针

        // 存放Node对象开始,每次都是new一个
        while (cur != null) {
            map.put(cur, new Node(cur.value));  // key是就节点,value是新节点
            cur = cur.next;
        }

        cur = head;  // 继续使用它,现在回到头节点
        while (cur != null) { // 运行结束条件
            // 一个是我们新的要拿值,一个是旧的给值
            // 通过map的value再取值           旧节点的值
            map.get(cur).next = cur.next;  // 存next
            map.get(cur).rand = cur.rand;  // 存rand
            cur = cur.next;  // 下一个
        }
        return map.get(head);
    }


    /*
    *
    * 不通过其它容器的方式
    *  每次链表出现一个跟屁虫,然后跟屁虫依据原来链表的next,rand继续跟屁虫...然后拆开
    *
    * */
    public static Node copyListWithRand2(Node head) {
        if (head == null) {  // 规范
            return null;
        }

        Node cur = head;   // 链表必备指针
        Node next = null; // 初始化next指针,这次主要用于找到old,next
        // copy node and link to every node
        while (cur != null) {
            next = cur.next;  // 先拿到自己的下一个
            cur.next = new Node(cur.value); // 新建了2号Node
            cur.next.next = next; // 我的下下家是二号
            cur = next; // 到1号的下一个了..
        }

        cur = head;  // 1号自己指针
        Node curCopy = null;  // 链表2号的自己指针,指向它自己
        // set copy node rand
        while (cur != null) {
            next = cur.next.next;  // 1号的next遍历
            curCopy = cur.next; // 2号的下一个,是1号的下一个(新节点)的下一个(老节点)的下一个(新节点)
            curCopy.rand = cur.rand != null ? cur.rand.next : null; // rand也一样,不过得防止null
            cur = next; // 下一波..
        }

        /*
        *
        * 成功复制上了,拆
        * */
        Node res = head.next;
        cur = head;
        // split
        while (cur != null) {
            next = cur.next.next;
            curCopy = cur.next;
            cur.next = next;
            curCopy.next = next != null ? next.next : null;
            cur = next;
        }
        return res;
    }

    public static void printRandLinkedList(Node head) {
        Node cur = head;
        System.out.print("order: ");
        while (cur != null) {
            System.out.print(cur.value + " ");
            cur = cur.next;
        }
        System.out.println();
        cur = head;
        System.out.print("rand:  ");
        while (cur != null) {
            System.out.print(cur.rand == null ? "- " : cur.rand.value + " ");
            cur = cur.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        Node head = null;
        Node res1 = null;
        Node res2 = null;
        printRandLinkedList(head);
        res1 = copyListWithRand1(head);
        printRandLinkedList(res1);
        res2 = copyListWithRand2(head);
        printRandLinkedList(res2);
        printRandLinkedList(head);
        System.out.println("=========================");

        head = new Node(1);
        head.next = new Node(2);
        head.next.next = new Node(3);
        head.next.next.next = new Node(4);
        head.next.next.next.next = new Node(5);
        head.next.next.next.next.next = new Node(6);

        head.rand = head.next.next.next.next.next; // 1 -> 6
        head.next.rand = head.next.next.next.next.next; // 2 -> 6
        head.next.next.rand = head.next.next.next.next; // 3 -> 5
        head.next.next.next.rand = head.next.next; // 4 -> 3
        head.next.next.next.next.rand = null; // 5 -> null
        head.next.next.next.next.next.rand = head.next.next.next; // 6 -> 4

        printRandLinkedList(head);
        res1 = copyListWithRand1(head);
        printRandLinkedList(res1);
        res2 = copyListWithRand2(head);
        printRandLinkedList(res2);
        printRandLinkedList(head);
        System.out.println("=========================");

    }

}
